⟸ pàgina anterior ⟸
Exercici 3 (Tasca 1).
(Kleene star, theory of languages)

Estrella de Kleene — propietats bàsiques

Justifiqueu les vostres respostes a les preguntes següents. Els llenguatges estan definits sobre un alfabet fixat qualsevol.

  1. Distribueix l’estrella de Kleene sobre la concatenació de llenguatges? És a dir, per tot parell de llenguatges L_1,L_2, es compleix que L_1^*L_2^*= (L_1L_2)^*? I si en lloc de “=” només es demana “\subseteq” o “\supseteq”? I si imposem L_1=L_2, es compleix ara? I si quan L_1=L_2, en lloc de “=” només es demana per “\subseteq” o “\supseteq”?
  2. Indueixen sempre les clausures positives particions no trivials? És a dir, per tot parell de llenguatges L_1,L_2, si L_1^+\cup L_2^+=\{a,b\}^+ i L_1^+\cap L_2^+=\emptyset, llavors o bé L_1=\emptyset o bé L_2=\emptyset.
  3. Distribueix l’estrella de Kleene sobre la reunió de llenguatges? És a dir, per tot parell de llenguatges L_1,L_2, es compleix que L_1^*\cup L_2^*= (L_1\cup L_2)^*? I si en lloc de “=” només es demana “\subseteq” o “\supseteq”?
  4. Distribueix l’estrella de Kleene sobre la intersecció de llenguatges? És a dir, per tot parell de llenguatges L_1,L_2, es compleix que L_1^*\cap L_2^*= (L_1\cap L_2)^*? I si en lloc de “=” només es demana “\subseteq” o “\supseteq”?
  5. És l’estrella de Kleene monòtona respecte de la inclusió? És a dir, per tot parell de llenguatges L_1,L_2, L_1\subseteq L_2 implica L_1^*\subseteq L_2^*? Es compleix la recíproca? És a dir, per tot parell de llenguatges L_1,L_2, L_1^*\subseteq L_2^* implica L_1\subseteq L_2? I si L_1=\{a,b\} i L_2 és un llenguatge sobre \{a,b\}, es compleix la recíproca en aquest context especial?
  6. Cadena d’inclusions. Es compleix per tot llenguatge L que \overline{L^*}\subseteq \overline{L}\subseteq \overline{L}^*? I si capgirem les inclusions? Es compleix \overline{L^*}\supseteq \overline{L}\supseteq \overline{L}^*?
  7. Condició suficient per estrelles de Kleene diferents. Donats dos llenguatges L_1, L_2 \not=\emptyset qualssevol, es compleix que L_1\cap L_2=\emptyset implica L_1^*\not=L_2^*?
  8. On és el tancament positiu al quadrat? Es compleix L^+L^+\subseteq L^+ per tot llenguatge L? Es compleix la inclusió inversa L^+L^+\supseteq L^+?